package 分类.一维动规;

import java.util.*;


class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
    public TreeNode(){};
    public TreeNode(TreeNode left,TreeNode right,int val){this.left=left;this.right=right;this.val=val;};
}
public class 打家劫舍3 {
    Map<TreeNode, Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        if(root==null) return 0;
        if(memo.containsKey(root)) return memo.get(root);
        int do_it=root.val+(root.left==null?0:rob(root.left.left)+rob(root.left.right))+(root.right==null?0:rob(root.right.left)+rob(root.right.right));
        int not_do_it=rob(root.left)+rob(root.right);
        int res = Math.max(do_it, not_do_it);
        memo.put(root, res);
        return res;
    }
}
